package com.njupt.HashTable;

import java.util.*;

public class ThreeSum {

    /**
     * 暴力解，三重for循环
     * @param nums
     * @return
     */
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> lists = new ArrayList<>();
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            for (int j = i+1; j < nums.length; j++) {
                for (int k = j+1; k < nums.length; k++) {
                    if(nums[i] + nums[j] + nums[k] == 0){
                        List<Integer> integers = new ArrayList<>();
                        integers.add(nums[i]); integers.add(nums[j]); integers.add(nums[k]);
                        if( !isContain(lists,integers)){
                            lists.add(integers);
                        }
//                        lists.add(integers);
                    }
                }
            }
        }

        return lists;
    }

    public boolean isContain(List<List<Integer>> lists,List<Integer> integers){
        for (List<Integer> list : lists) {
            if(list.contains(integers.get(0)) && list.contains(integers.get(1)) && list.contains(integers.get(2))){
                return true;
            }
        }
        return false;
    }

    /**
     *
     * 哈希法，让i遍历a，j遍历b，剩余c = 0-（a+b）
     * @param nums
     * @return
     */
    public List<List<Integer>> threeSum1(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            //若排序之后的要判断的三元组的第一个元素大于0，那么之后的元素不可能
            if(nums[i]>0){
                break;
            }
            //三元组元素a去重
            if(i>0 && nums[i] == nums[i-1]){
                continue; //剪枝
            }
            Set<Integer> set = new HashSet<>();
            for (int j = i+1; j < nums.length ; j++) {
                //三元组元素b去重
                if(j>i+2 && nums[j] == nums[j-1] && nums[j-1] == nums[j-2]){
                    continue; //剪枝
                }
                int c = 0 - (nums[i] + nums[j]);
                if(set.contains(c)){
                    result.add(Arrays.asList(nums[i],nums[j],c));
                    set.remove(c);  //三元组元素c去重
                }else {
                    set.add(nums[j]);
                }
            }

        }
        return result;
    }

    /**
     * 双指针法。首先i指针确定一个值numn[i] = a;
     * 剩下的两个值交给双指针确定
     * @param nums
     * @return
     */
    public List<List<Integer>> threeSum2(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums);
        int num = -1;
        for (int i = 0; i < nums.length; i++) {

            if(nums[i]>0){
                break;
            }
            //三元组元素a去重
            if(i>0 && nums[i] == nums[i-1]){
                continue; //剪枝
            }
            int left = i+1;
            int right = nums.length -1;
            while(left<right){
                 num = nums[i] + nums[left] + nums[right];
                 if(num>0){
                     right--;
                 } else if (num<0) {
                     left++;
                 }else {
                     result.add(Arrays.asList(nums[i] ,nums[left] ,nums[right]));
                     while(left<right && nums[left] == nums[left+1]) left++;
                     while(left<right && nums[right] == nums[right-1]) right--;
                     left ++;
                     right--;
                 }
            }
        }


        return result;
    }



    public static void main(String[] args) {
        int[] nums = {-4,-2,1,-5,-4,-4,4,-2,0,4,0,-2,3,1,-5,0};
//        int[] nums = {-1,0,1,5,-1,-4};
        ThreeSum test = new ThreeSum();
        List<List<Integer>> lists = test.threeSum2(nums);
        Iterator<List<Integer>> iterator = lists.iterator();
        while(iterator.hasNext()){
            System.out.println(iterator.next());
        }
    }
}
